package dp;

/**
 * @Description 718. 最长重复子数组 https://leetcode.cn/problems/maximum-length-of-repeated-subarray/
 * @Author Firenut
 * 参考视频题解: https://www.bilibili.com/video/BV1eC4y187NR/?spm_id_from=333.337.search-card.all.click&vd_source=e9c8c28654af81fbd6bef7c83b93afa4
 * @Date 2023-02-20 17:48
 */

// 将两个一维数组转成二维数组的行和列进行比较,如果相同则
// 定义: dp[i][j]表示 在数组nums1、nums2中,以 nums1[i]、nums2[j]结尾的两个字符串的最大重复字符串的长度
// 初始值: 默认dp[i][j] = 0
// 状态转移方程:
//      dp[i][j] = dp[i-1][j-1]+1  (nums1[i] == nums2[j] && i >= 1 && j >= 1)  防止dp[i-1][j-1]越界
//      dp[i][j] = 1 (nums1[i] == nums2[j] && !(i >= 1 && j >= 1))
//      dp[i][j] = 0 (nums1[i] != nums2[j])
// 返回值: max(dp[i][j])
public class T718_findLength {
    public int findLength(int[] nums1, int[] nums2) {
        int[][] dp = new int[nums1.length][nums2.length];
        int max = 0;
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                if (nums1[i] == nums2[j]) {
                    if (i >= 1 && j >= 1) {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    } else {
                        dp[i][j] = 1;
                    }
                } else {
                    dp[i][j] = 0;
                }
                max = Math.max(dp[i][j], max);
            }
        }
        return max;
    }
}